"""
对链表值进行分区
挑战介绍
实现一个算法来对链表中结点的元素值进行分区，使所有小于 x 的节点排在所有大于或等于 x 的节点之前。要求如下：

对于给定值 x，将链表的结点的顺序排为：值小于 x 的结点，值等于 x 的结点，值大于 x 的结点。
对于分区的每部分，即值小于 x 的部分和值大于 x 的部分，不需要按值的大小再进行排序，而是按照原本链表的顺序进行链接。例如值为 [4, 8, 5, 2, 5] 的链表按 5 进行分区的结果为 [4, 2, 5, 5, 8]。
挑战内容
本次挑战中，你需要在 partition_data.py 文件中补充函数 partition 的空缺部分。

MyLinkedList 类继承“实现链表类”挑战中的 LinkedList 类。
MyLinkedList 类的 partition 方法用于对链表中结点的元素值进行分区，参数 data 用于指定分区的临界值，它需要返回分区后的链表。
如果链表没有结点，则不进行分区操作。
"""
from linked_list import LinkedList


class MyLinkedList(LinkedList):

    def partition(self, data):
        if self.head is None:
            return
        left = MyLinkedList(None)
        right = MyLinkedList(None)
        curr = self.head

        # Build the left and right lists
        while curr is not None:
            if curr.data < data:
                left.append(curr.data)
            elif curr.data == data:
                right.insert_to_front(curr.data)
            else:
                right.append(curr.data)
            curr = curr.next
        curr_left = left.head
        if curr_left is None:
            return right
        else:
            # Merge the two lists
            while curr_left.next is not None:
                curr_left = curr_left.next
            curr_left.next = right.head
            return left
